package Parser;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;

public class Parser {
	final static String END_SYMBOL = "ENDSYMBOL";
	final static String EMPTY_STRING = "EMPTYSTRING";

	public static void printSet(Map<String, Set<String>> map) {
		Iterator<Entry<String, Set<String>>> keyIter = map.entrySet().iterator();

		while(keyIter.hasNext()) {
			StringBuilder sb = new StringBuilder();
			Entry<String, Set<String>> nextEntry = keyIter.next();
			String [] elements = nextEntry.getValue().toArray(new String[0]);
			sb.append(nextEntry.getKey())
			.append(" : ");
			for(String s : elements) {
				sb.append(s)
				.append(" ");
			}
			System.out.println(sb.toString());
		}
	}

	private String globalKey;

	/**
	 * Get the first set of all rules
	 * Expects rules to have been expanded, left recursion removed, 
	 * 	common prefixes removed, etc..
	 * @param rulesList -- from Run.java
	 * @return
	 * 
	 * TODO: Needs testing
	 * 		 
	 */
	public Map<String, Set<String>> getFirstSet(ArrayList<Rule> rulesList) {
		Map<String, Set<String>> firstSet = new HashMap<String, Set<String>>();

		// First(A) = {}
		for(Rule rule : rulesList) {
			String title = rule.getTitle();
			if(!firstSet.containsKey(title)) {
				firstSet.put(title, new HashSet<String>());
			}
		}

		boolean changeOccured = false;
		boolean alreadyHasEmptyString = false;
		do {
			changeOccured = false;
			// Go through all the rules
			for(int i = 0; i < rulesList.size(); i++) {
				Rule rule = rulesList.get(i);
				Set<String> oldSet = firstSet.get(rule.getTitle());
				// Go through the rule's body
				int k = 0;
				for(k = 0; k < rule.getBodySize(); k++) {
					// Easier than doing a deep copy
					int oldSize = oldSet.size();
					String element = rule.getElement(k);
					if(oldSet.contains(EMPTY_STRING)) {
						alreadyHasEmptyString = true;
					}
					if(rule.isNonTerminal(element)) {
						oldSet.addAll(firstSet.get(element));
					} else {
						oldSet.add(element);
					}
					if(oldSet.contains(EMPTY_STRING) && !alreadyHasEmptyString) {
						oldSet.remove(EMPTY_STRING);
						changeOccured = (oldSize < oldSet.size()) ? true : changeOccured;
						continue;
					}
					changeOccured = (oldSize < oldSet.size()) ? true : changeOccured;
					break;
				}
				if(k == rule.getBodySize()) {
					oldSet.add(EMPTY_STRING);
				}
			}	
		}while(changeOccured);


		return firstSet;
	}

	public Map<String, Set<String>> getFollowSet(ArrayList<Rule> rulesList, String start) {
		Map<String, Set<String>> firstSet = getFirstSet(rulesList);
		Map<String, Set<String>> followSet = new HashMap<String, Set<String>>();

		// Follow(A) = {$} or {}
		for(Rule rule : rulesList) {
			String title = rule.getTitle();
			if(!followSet.containsKey(title)) {
				followSet.put(title, new HashSet<String>());
				if(title.equals(start)) {
					followSet.get(title).add(END_SYMBOL);
				}
			}
		}

		// While there are changes in any Follow(A)...
		boolean changeOccured = false;
		do {
			changeOccured = false;
			for(Rule rule : rulesList) {
				// Go up to second to last element
				int i = 0;
				for(i = 0; i < rule.getBodySize() - 1; i++) {
					String currentElement = rule.getElement(i);
					if(rule.isNonTerminal(currentElement)) {
						Set<String> oldSet = followSet.get(currentElement);
						int oldSize = oldSet.size();
						String nextElement = rule.getElement(i+1);
						if(rule.isNonTerminal(nextElement)) {
							oldSet.addAll(firstSet.get(nextElement));
						} else {
							oldSet.add(nextElement);
						}
						if(oldSet.contains(EMPTY_STRING)) {
							oldSet.remove(EMPTY_STRING);
							oldSet.addAll(followSet.get(rule.getTitle()));
						}

						changeOccured = (oldSize < oldSet.size()) ? true : changeOccured;
					}
				}
				String lastElement = rule.getElement(i);
				if(rule.isNonTerminal(lastElement)) {
					Set<String> lastSet = followSet.get(lastElement);
					int lastSize = lastSet.size();					
					lastSet.addAll(followSet.get(rule.getTitle()));
					lastSet.add(END_SYMBOL);
					changeOccured = (lastSize < lastSet.size()) ? true : changeOccured;
				}
			}
		} while(changeOccured);

		return followSet;
	}

	/**
	 * XXX Changed a few data structures, hope I didn't break it! -Sergy Nall
	 * Lee -- no it's fine.  I said at one point to use sets because they'll
	 * enforce uniqueness
	 * 
	 * @param firstSet
	 * @param followSet
	 * @param ruleList
	 * @return
	 */
	public Map<String, Rule> getParseTable(Map<String, Set<String>> firstSet, 
			Map<String, Set<String>> followSet, ArrayList<Rule> ruleList) {

		HashMap<String, Rule> parseTable = new HashMap<String, Rule>();
		for (String firstKey: firstSet.keySet()) {
			globalKey = firstKey;
			Set<String> firstList = firstSet.get(firstKey);
			for (String firstMember: firstList) {
				String orderedPair = firstKey + " " + firstMember;
				if (!firstMember.equals("EMPTYSTRING")) {
					Rule rule = look(ruleList, firstMember);
					parseTable.put(orderedPair, rule);
				}

				else {
					String followKey = null;
					for (String follow: followSet.keySet()) {
						if (follow.equals(firstKey)) { 
							followKey = follow;
							break;
						}
					}
					if (followKey == null) continue;
					Set<String> followList = followSet.get(followKey);
					for (String followMember: followList) {
						String orderedPairFollow = followKey + " " + followMember;
						Rule rule = new Rule(followKey + " : EMPTYSTRING");
						parseTable.put(orderedPairFollow, rule);
					}
				}
			}
		}
		return parseTable;
	}

	private Rule look(ArrayList<Rule> ruleList, String firstMember) {
		Rule r = new Rule();
		for (Rule e: ruleList) {
			if (e.getElement(0).equals(firstMember)) {
				r = e;
			}
		}
		if (r.getTitle().equals(globalKey)) return r;
		else return look(ruleList, r.getTitle());
	}

	/**
	 * Basic print method for debugging
	 * 
	 * @param parseTable
	 */
	public void printTable(Map<String, Rule> parseTable) {
		int counter = 1;
		for (String pair: parseTable.keySet()) {
			String[] e = pair.split(" ");
			System.out.println("PAIR " + counter + ": " + e[0] + ", " + e[1]);
			System.out.println("RULE: " + parseTable.get(pair) + "\n");
			counter++;
		}
	}

	/**
	 * Parse() is the main parsing algorithm implemented (I hope) according 
	 * to the class slides.
	 * 
	 * @param parseTable
	 * @param tokens
	 * @param nonTerminals
	 * @param start
	 * @return
	 */
	public boolean parse(Map<String, Rule> parseTable, String[] tokens, String start) {
		boolean retVal = false;
		ArrayList<String> nonTerminals = new ArrayList<String>();
		for (String e: parseTable.keySet()) {
			String[] elements = e.split(" ");
			nonTerminals.add(elements[0]);
		}
		Stack<String> parseStack = new Stack<String>();
		parseStack.push(END_SYMBOL);
		parseStack.push(start);

		for (String currentToken: tokens) {
			while (true) {

				String topOfStack = parseStack.peek();
				boolean isNonTerminal = false;
				for (String e: nonTerminals) { 
					if (topOfStack.equals(e)) {
						isNonTerminal = true;
						break;
					}
				}

				if (isNonTerminal) {
					String currentStackValue = parseStack.pop();
					String orderedPair = currentStackValue + " " + currentToken;
					Rule currentRule = parseTable.get(orderedPair);
					if (currentRule == null) System.out.println(orderedPair);
					String currentRuleBody = currentRule.getBody();
					String[] elements = currentRuleBody.split(" ");
					for(int i = elements.length - 1; i >= 0; i--) {
						parseStack.push(elements[i]);
					}
					continue;
				}

				else {
					if (topOfStack.equals(currentToken)) { 
						parseStack.pop();
						break;
					}
					else {
						if (topOfStack.equals("EMPTYSTRING")) {
							parseStack.pop();
							continue;
						}
						else {
							System.out.println("UNSUCCESSFUL PARSE");
							System.out.println("CURRENT TOKEN: " + currentToken);
							System.out.println("STACK DUMP:");
							while(!parseStack.isEmpty()) System.out.print(parseStack.pop() + " ");
							return false;
						}
					}
				}
			}
		}

		while (true) {
			String tester = parseStack.peek();
			String orderedPair = tester + " " + END_SYMBOL;
			Rule testRule = parseTable.get(orderedPair);
			if (testRule != null && testRule.getBody().equals("EMPTYSTRING")) {
				parseStack.pop();
				continue;
			}
			else break;
		}

		String isSuccessful = parseStack.pop();
		if (isSuccessful.equals(END_SYMBOL)) {
			retVal = true;
			System.out.println("SUCCESSFUL PARSE!");
		}
		else {
			System.out.println("UNSUCCESSFUL PARSE");
		}
		return retVal;

	}
}
